package sort;

import comment.Comment;


/**
 *create by tbj
 */
public class QuickSort_One {
	private static int partition(int[] a,int l,int r){
		// 对arr[l...r]部分进行partition操作
	    // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
					/*优化  尽可能的让v是随机数，防止近乎顺序的数组退化后的运行复杂度为O（n^2）
						随机取后，期望的复杂度是O（NlogN）,为O（n^2）的概率几乎为零*/
		Comment.swapIntArr(a, l, (int)Math.random()*(r-l+1)+l);//优化语句
		int v=a[l];
		// arr[l+1...j] < v ; arr[j+1...i) > v
		int j=l;
		for(int i=l+1;i <= r;i++){
			if(a[i]<v){
				Comment.swapIntArr(a, j+1, i);;
				j++;
			}
		}
		Comment.swapIntArr(a, l, j);
		return j;
	}
	private static void _sort(int[] a,int l, int r){
		if(l >= r){ //优化  可以当元素数据量小到一定值时（r-l <= x），进行另外的排序（如插入排序）
			return;
		}
		int p=partition(a,l,r);
		_sort(a,l,p-1);
		_sort(a,p+1,r);
	}
	
	public static void sort(int[] a){
		int n=a.length;
		_sort(a,0,n-1);
	}
	public static void main(String[] args) {
		int[] a=Comment.getRandIntArr(500000);
		long t1=System.currentTimeMillis();
		QuickSort_One.sort(a);
		long t2=System.currentTimeMillis();
		System.out.println(t2-t1);
		int[] b=Comment.getRandIntArr(500000);
		long t3=System.currentTimeMillis();
		MergeSort.sort(b);
		long t4=System.currentTimeMillis();
		System.out.println(t4-t3);
		
	}
}
